package com.ycy.leetcode.tree;


import org.junit.Before;
import org.junit.Test;

import java.util.LinkedList;

/**
 * 打印树的查询路径
 * <p>
 * 查找一棵树的公共祖先
 * <p>
 * 检查是不是一颗搜索树
 */
public class TreeSearch {

  @Test
  //二叉树获取查询路径
  public void test1() {
    /**
     *     1
     *  2     3
     * 4 5    7 8
     *    9
     */
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    root.left.right.right = new TreeNode(9);

    root.right = new TreeNode(3);
    root.right.left = new TreeNode(7);
    root.right.right = new TreeNode(8);

    lujing(root, 9);
    System.out.println(list);
    for (TreeNode o : list) {
      System.out.println(o.val);
    }

  }


  static LinkedList<TreeNode> list = new LinkedList();

  /**
   * 二叉树的查询路径， 对于平衡二叉树 和 二叉树都是通用的
   *
   * @param node
   * @param target
   * @return
   */
  public boolean lujing(TreeNode node, int target) {
    if (node == null) return false;
    list.addLast(node);
    if (node.val == target) return true;
    //这个find 很重要，如果在当前节点下查询不到，需要通过这个标识 把节点从队列中移除
    boolean find = false;
    if (node.left != null) {
      find = lujing(node.left, target);
    }
    if (node.right != null) {
      find = lujing(node.right, target);
    }
    if (!find) list.removeLast();
    return find;
  }

  //检查一个树 是不是一个搜索树
  @Test
  public void test2() {
    /**
     *     100
     *  50     200
     * 25 5    7 8
     *     9
     */
    TreeNode root = new TreeNode(100);
    root.left = new TreeNode(50);
    root.left.left = new TreeNode(25);
    root.left.right = new TreeNode(5);
    root.left.right.right = new TreeNode(9);

    root.right = new TreeNode(200);
    root.right.left = new TreeNode(7);
    root.right.right = new TreeNode(8);

    //测试是不是中序遍历
    System.out.println(bsttreeCheck(root));
    System.out.println(order);

  }

  LinkedList<Integer> order = new LinkedList<>();

  /**
   * 检查是不是一颗搜索树
   */
  public boolean bsttreeCheck(TreeNode treeNode) {
    //null 返回
    if (treeNode == null) return true;


    boolean b = true;

    if (treeNode.left != null) {
      b = bsttreeCheck(treeNode.left);
      if (!b) return false;
    }

    //这一步告诉我们 这个树 不是bst树,返回false
    if (!order.isEmpty() && order.getLast() > treeNode.val) return false;

    order.add(treeNode.val);

    if (treeNode.right != null) {
      b = bsttreeCheck(treeNode.right);
      if (!b) return false;
    }
    return b;
  }

  TreeNode root = null;

  @Before
  public void before() {
    /**
     *     100
     *  50     200
     * 25 5    7 8
     *     9
     *     10
     */
    this.root = new TreeNode(100);
    root.left = new TreeNode(50);
    root.left.left = new TreeNode(25);
    root.left.right = new TreeNode(5);
    root.left.right.right = new TreeNode(9);
    root.left.right.right.right = new TreeNode(10);

    root.right = new TreeNode(200);
    root.right.left = new TreeNode(7);
    root.right.right = new TreeNode(8);


  }

  //获取一棵树的最大深度
  @Test
  public void test3() {
    System.out.println("ab".substring(1,1));

    maxDepth(root, 0);
    System.out.println(i);
  }

  int i = 0;

  /**
   * 最大数深度
   */
  public void maxDepth(TreeNode treeNode, int i) {
    if (treeNode == null) return;

    i += 1;
    if (i > this.i) this.i = i;
    maxDepth(treeNode.left, i);
    maxDepth(treeNode.right, i);

  }

}
